This application relates generally to the copending application entitled "Minimizing The Interconnection Cost of Electronically Linked Objects" filed on an even date herewith.
Complex electronic circuits have traditionally been designed in two phases: logical design and physical design. Logical design is the process for defining the correct operation of the circuit and the necessary components to achieve that operation. Physical design includes the placement or layout of the logical design to meet the physical constraints of the hardware.
A major problem in this design process for modern electronic systems has been the positioning of the components or models and the routing of their connections on the physical layout of the semiconductor chip in a manner which maximizes design performance, i.e., speed. The semiconductor chip only has a fixed area which accommodates a set number of placement slots to hold the models. Also, the semiconductor chip only has a fixed number of external terminals or pins by which the models located thereon can be coupled to other semiconductor chips. Other constraints which must be accounted for in the electronic physical design of the chip include the operational or mechanical considerations which dictate that a particular set of models must be on the same chip or that certain models must be on different chips.
With the advent of very large scale integrated circuits (VLSI), and their mass production, the number of placement slots that can be placed in a limited area has increased dramatically. The placement of the logical design on the semiconductor chips must now be achieved with respect to the size of the chips, constraints on design performance, and the time necessary to solve the layout design. Therefore, not only must the layout be an efficient design but also the development of the layout must be performed efficiently.
In order to fully understand the field of the invention the following glossary of terms are set forth and are used throughout the specification:
A "model" is an indivisible logic function block, e.g., AND gate, OR gate, XOR gate, etc.
A "port" is any input or output of a model.
A "signal" is a set of electrically common ports.
A "load" is defined as the input port to a model.
A "driver" is defined as the output port from a model.
A "connection" is a single path between two ports of a signal.
A "path" is a sequence of connections, ports, and models along which an electrical signal travels.
A "design" is the collection of named models, ports, and signals.
The word "partition" is used interchangeably as both a noun and a verb in the following description, i.e. a set of models is partitioned into further partitions, and these further partitions are disjoint and collectively exhaustive.
A "cut-set" is the set of connections linking models which have been assigned to different partitions.
The "cost" of a partition is the weighted sum of the costs of the connections in its cut-set.
A "location" of a port or model is a unique (x, y) coordinate which fixes the port or model position on the substrate.
The "delay" of a model or signal connection is the amount of time required to pass a signal through the model or connection. Path delays are the sum of model and signal delays along a path.
A "timing constraint" is the maximum allowable delay along a path. The maximum allowable delay may include both signal connection and model delays.
A "timing debt" is the number of time units by which the path delay exceeds the worst case timing constraint.
A "critical driver/load" is a driver or load in a cut-set having a delay approaching that of the timing constraint.
A "noncritical driver/load" is a driver or load in a cut-set having a delay that does not approach that of the timing constraint.
A "placement slot" is a location at which a model may be placed on the substrate.
A "swap" is the action of exchanging the contents of two different placement slots.
The total "gain" of a swap of two models is the sum of the costs of its connections at the old locations minus the sum of the costs of its connections at the new locations. Gain can be negative or positive.
The "partial gain" of a model is that part of the total gain which results from moving one model to another partition.
An "ordered bucket vector" is a linked list data structure existing for each partition to order the models in accordance with their partial gains. The ordered bucket vector allows for the fast insertion or deletion of the model from the linked list structure.
The "cumulative gain" is the sum of the gains of a sequence of swaps. The cumulative gain therefore may also be either positive or negative.
One prior known method for the placement of electrical components or models by partitioning makes use of a cost matrix to define the cost of connecting a particular model to each of the other models on the chip. The method initially defines an arbitrary partition of the models in the logical design. The cost matrix is then used to compute the total cost of the connections between the sets of the partition, wherein each set represents a supporting structure, i.e., each set may itself contain interconnections of models. A series of interchanges of particular subsets within each set are attempted to decrease the total interconnection cost. Once no further improvements are possible, the resulting partitions are stored and the process is repeated with a randomly different initial partition. Each resulting partition is potentially an improved solution, and any particular partition may be used to assign models to locations on the semiconductor chips.
A problem with the previous known partitioning methods is that the partitioning neglects important electrical properties of the connections between models. Some of the prior methods do not factor into account the relationship between time-critical drivers and loads of the models (wherein one model has an output port which drives the input port of another model) or do so in an inefficient manner. The existing partitioning methods either ignore signals with more than three ports entirely or consider all connections of a signal uniformly, i.e., there is no distinction between connections of a signal. As a result, bad solutions which place critical connections in a cut-set appear equivalent to good solutions which contain them within a partition.